package com.cris.search;

/**
 * Created by owen on 2017/3/30.
 */

/**
 * 基于有序数组的二分查找，没有完全实现
 * @param <Key>
 * @param <Value>
 */
public class BinarySearchST<Key extends Comparable<Key>,Value> {
    private static final int INIT_CAPACITY = 2;
    private Key[] keys;
    private Value[] vals;
    private int n = 0;

    /**
     * Initializes an empty symbol table.
     */
    public BinarySearchST() {
        this(INIT_CAPACITY);
    }

    /**
     * Initializes an empty symbol table with the specified initial capacity.
     * @param capacity the maximum capacity
     */
    public BinarySearchST(int capacity) {
        keys = (Key[]) new Comparable[capacity];
        vals = (Value[]) new Object[capacity];
    }

    // resize the underlying arrays
    private void resize(int capacity) {
        assert capacity >= n;
        Key[]   tempk = (Key[])   new Comparable[capacity];
        Value[] tempv = (Value[]) new Object[capacity];
        for (int i = 0; i < n; i++) {
            tempk[i] = keys[i];
            tempv[i] = vals[i];
        }
        vals = tempv;
        keys = tempk;
    }
    public int size(){
        return n;
    }
    public boolean isEmpty(){
        return size()==0;
    }
    public Value get(Key key){
        int i = rank(key);
        if(isEmpty()) return null;
        if(i<n&&keys[i].compareTo(key)==0) return vals[i];
        else return null;
    }

    /**
     * 递归的二分查找
     * @param key
     * @return
     */
    public int rank(Key key,int lo,int hi){
        if(lo>hi) return lo;
        int mid=lo+(hi+lo)/2;
        int cmp = key.compareTo(keys[mid]);
        if(cmp<0) return rank(key,lo,mid-1);
        else if(cmp>0) return rank(key,mid+1,hi);
        else return mid;
    }
    /**
     * 非递归的二分查找
     * 此函数返回键在有序数组小于它的键的数量
     */
    public int rank(Key key){
        int lo =0;
        int hi=n-1;
        while(hi>=lo){
            int mid = (lo+hi)/2+lo;
            int cmp = key.compareTo(keys[mid]);
            if(cmp<0) hi = mid-1;
            else if(cmp>0) lo = mid+1;
            else return mid;
        }
        return lo;
    }




}
